In computing systems, a cache is a component that stores data so that subsequent requests for that same data can be provided faster. The cache may be implemented using any type of storage component, including for example, memory components for memory caches and disk components for disk caches.
A “cache hit” occurs when the requested data can be found in a cache. This means that the requested data can be directly served from cache rather than requiring the expense of having the requested data to be created and/or retrieved from another system. In contrast, a “cache miss” occurs when the requested data cannot be served from the cache. In this situation, additional time and/or expenses (e.g., computational expenses, network expenses, I/O expenses) will need to be incurred to obtain the requested data.
As is evident, it is generally the case that the more that requests can be served from the cache, the faster a given system can perform. The problem is that caches are expensive to implement, and the larger the cache, the more expensive it is to implement that cache. A cache that is sized too large is wasteful, since it will not receive enough benefit from the extra cache portions beyond what it really needs to offset the cost of that excess (and likely underutilized) cache. On the other hand, implementing a cache that is too small will likely result in performance problems due to excessive cache misses.
Miss Rate Curves (MRC) have been generated to attempt to address this problem, by tracking or estimating cache usage to attempt to determine the miss rates for a given cache size. The problem is that conventional MRC algorithms require large amounts of memory to keep track of how the cache is being used. For example, estimating cache hit ratios (the cache hit ratio is one minus the cache miss ratio) given a particular cache size traditionally demands prohibitive memory consumption requirements, which is often linear with the working set size. As the size of the working set grows larger, the amount of memory needed to compute the MRC also grows larger, causing excessive computing inefficiencies and lack of scalability. The computational demands of the conventional approaches increase with the product of working set size and the request rate. There have been improvements to reduce the complexity of the computational demands to logarithmic in I/O rate, but the memory space requirements remain linear with working-set size.
Therefore, there is a need for an improved and more memory-efficient approach to implement cache size estimations.